import java.util.ArrayList;
import java.util.HashMap;

public class demo02 {
    //数组中出现次数超过一半的数字
//    public static int MoreThanHalfNum_Solution (int[] numbers) {
//        HashMap<Integer,Integer> map=new HashMap<>();
//        for (int i = 0; i < numbers.length; i++) {
//            if(map.get(numbers[i])!=null){
//                map.put(numbers[i],map.get(numbers[i])+1);
//            }else{
//                map.put(numbers[i],1);
//            }
//        }
//        for (int i = 0; i < numbers.length; i++) {
//            if(map.get(numbers[i])>numbers.length/2){
//                return numbers[i];
//            }
//        }
//        return -1;
//    }
    public static int MoreThanHalfNum_Solution (int[] numbers) {
        if(numbers==null||numbers.length==0){
            return 0;
        }
        int time=1;
        int num=numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            if (time!=0){
                if(num==numbers[i]){
                    time++;
                }else{
                    time--;
                }
            }else {
                time=1;
                num=numbers[i];
            }
        }
        time=0;
        for (int i = 0; i < numbers.length; i++) {
            if(num==numbers[i]){
                time++;
            }
        }
        return time>numbers.length/2?num:0;
    }

    public static void main(String[] args) {
        int[] arr={1,2,3,2,2,2,5,4,2};
        System.out.println(MoreThanHalfNum_Solution(arr));
    }
}
